//
// Created by lanlu on 2025/8/8.
//

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr){}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right){}
};

class Solution {
public:

    void printVector(vector<int> &vec)
    {
        for (int i : vec)
        {
            cout << i << " ";
        }
        cout << endl;
    }
    // 第一次 [3,4,2,1,5]  [4,3,2,5,1]
    // 第二次 [3,4,2]      [4,3,2]          右 [5] [5]
    // 第三次 [3,4]        [4,3]
    // 第四次 [4]          [4]
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 递归出口
        if (inorder.empty() || postorder.empty()) return nullptr;

        printVector(inorder);
        printVector(postorder);

        // 递归规律
        int rootVal = postorder.back();
        TreeNode* root = new TreeNode(rootVal);
        // find返回的是迭代器 就是地址 减去起始位置 就是左子树的长度 也是索引
        int leftSize = find(inorder.begin(), inorder.end(), rootVal) - inorder.begin();
        // 切分左子树 这里是左闭右开
        // [3,4,2,1,5]  [4,3,2,5,1]  leftSize=3
        // [3,4,2]      [4,3,2]
        vector<int> leftInorder(inorder.begin(), inorder.begin() + leftSize);
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftSize);
        root -> left = buildTree(leftInorder, leftPostorder);

        // 切分右子树
        // [3,4,2,1,5]  [4,3,2,5,1]  leftSize=3
        // [5]          [5]
        // end()指最后一个元素的下一个  相当于右子树的中序结果和后序结果位置相差一位 就是根节点的位置
        vector<int> rightInorder(inorder.begin() + leftSize + 1, inorder.end());
        vector<int> rightPostorder(postorder.begin() + leftSize, postorder.end() - 1);
        root -> right = buildTree(rightInorder, rightPostorder);

        return root;
    }
};

int main()
{
    // TreeNode * root = new TreeNode(1);
    // TreeNode * node1 = new TreeNode(2);
    // TreeNode * node2 = new TreeNode(3);
    // TreeNode * node3 = new TreeNode(4);
    // TreeNode * node4 = new TreeNode(5);
    // root -> left = node1;
    // root -> right = node4;
    // node1 -> left = node2;
    // node2 -> right = node3;

    vector<int> inorder = {3,4,2,1,5};
    vector<int> postorder = {4,3,2,5,1};
    auto tree = Solution().buildTree(inorder,postorder);
}